Trong khi Hội nghị Fontainebleau đang diễn ra, ở Việt Nam, Chính phủ Liên hiệp lâm vào cảnh rạn nứt giữa phe Việt Minh và Việt Nam Quốc dân Đảng. Việt Minh cáo buộc Việt Nam Quốc dân Đảng thủ tiêu các cán bộ của mình,[16] cũng như câu kết với quân đội Pháp tạo cớ gây hấn nhằm thực hiện đảo chính. Ngược lại Quốc dân đảng cũng cáo buộc Việt Minh hợp tác với Pháp vì phe Quốc dân Đảng, nhất là đảng Đại Việt chống mãnh liệt Hiệp định sơ bộ Pháp-Việt 1946 ký kết giữa Việt Nam Dân chủ Cộng hòa và Pháp hồi tháng 3 năm 1946. Theo thỏa thuận đó thì quân Pháp được quyền tiến ra miền Bắc thay thế quân Trung Hoa Quốc dân Đảng (lực lượng hậu thuẫn cho Đại Việt, Việt Quốc, Việt Cách) và nhà chức trách Pháp đã cung cấp hỏa lực giúp Việt Minh đánh dẹp các căn cứ của Quốc dân Đảng.[17][18]

Ngày 15/6/1946, người lính cuối cùng của quân đội Trung Hoa Dân Quốc rời khỏi Việt Nam, Võ Nguyên Giáp vội vã từng bước tìm cách loại bỏ dần các đảng phái khác như Việt Quốc, Việt Cách, Đại Việt, những người Trotskist, lực lượng chính trị Công giáo... Ngày 19/6/1946, Báo Cứu Quốc của Tổng bộ Việt Minh đăng xã luận kịch liệt chỉ trích "bọn phản động phá hoại Hiệp định sơ bộ Pháp Việt mùng 6 tháng 3". Ngay sau đó Võ Nguyên Giáp bắt đầu chiến dịch truy quét các đảng phái khác bằng lực lượng công an và quân đội do Việt Minh kiểm soát với sự giúp đỡ của nhà cầm quyền Pháp. Ông cũng sử dụng các sĩ quan Nhật Bản trốn tại Việt Nam và một số vũ khí do Pháp cung cấp cho chiến dịch này.[19] Một trong những sự kiện nổi tiếng nhất trong chiến dịch tiêu diệt các đảng phái đối lập là vụ án phố Ôn Như Hầu.